package com.sakura.二叉树;

public class Code222_完全二叉树的节点个数 {

    
     // Definition for a binary tree node.
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode() {}
          TreeNode(int val) { this.val = val; }
          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

    public static void main(String[] args) {
        Code222_完全二叉树的节点个数 code222 = new Code222_完全二叉树的节点个数();
        TreeNode root = new Code222_完全二叉树的节点个数().new TreeNode(1);
        root.left = new Code222_完全二叉树的节点个数().new TreeNode(2);
        root.right = new Code222_完全二叉树的节点个数().new TreeNode(3);
        root.left.left = new Code222_完全二叉树的节点个数().new TreeNode(4);
        root.left.right = new Code222_完全二叉树的节点个数().new TreeNode(5);
        root.right.left = new Code222_完全二叉树的节点个数().new TreeNode(6);
        System.out.println(code222.countNodes(root));
    }

    public int countNodes(TreeNode root) {
          if(root == null) {
              return 0;
          }

          // 向左遍历
          TreeNode leftNode = root.left;
          int leftDepth = 0;
          while(leftNode != null) {
              leftNode = leftNode.left;
              leftDepth++;
          }
          // 向右遍历
          TreeNode rightNode = root.right;
          int rightDepth = 0;
          while(rightNode != null) {
              rightNode = rightNode.right;
              rightDepth++;
          }
          // 利用满二叉树的特点
          if (leftDepth == rightDepth) {
              return (2 << leftDepth) - 1;
          }
          return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
